class MinHeap {
    constructor(){
        this.arr = []
    }
    getParentIndex(i){
        return Math.floor((i-1)/2)
    }
    getLeftChildIndex(i){
        return i*2 + 1
    }
    getRightChildIndex(i){
        return i*2 + 2
    }
    insert(n){
        this.arr.push(n)
        const theIndex = this.arr.length -1
        this.toUp(theIndex)
    }

    toUp(i){
        if(i === 0)return
        const parentIndex = this.getParentIndex(i)
        const n = this.arr[i]
        if(this.arr[parentIndex] > n ){
            const temp = this.arr[parentIndex]
            this.arr[parentIndex] = n
            this.arr[i] = temp

            this.toUp(parentIndex)
        }
    }
    toDown(i){
        const leftIndex = this.getLeftChildIndex(i)
        const rightIndex = this.getRightChildIndex(i)

        if(leftIndex >= this.arr.length)return;
        if(this.arr[leftIndex] < this.arr[i]){
            const temp = this.arr[i]
            this.arr[i] = this.arr[leftIndex]
            this.arr[leftIndex] = temp
            this.toDown(leftIndex)
        }  
        
        if(this.arr[rightIndex] < this.arr[i]){
            const temp = this.arr[i]
            this.arr[i] = this.arr[rightIndex]
            this.arr[rightIndex] = temp
            this.toDown(rightIndex)
        }


    }
    getLen(){
        return this.arr.length
    }
    shift(n){
        this.arr[0] = n
        this.toDown(0)
    }
    getTop(){
        return this.arr[0]
    }
}

var findKthLargest = function(nums, k) {
    let heap = new MinHeap
    nums.forEach(v => {
        
        if(heap.getLen() < k){
            heap.insert(v)
        }else if(heap.getTop() < v){
            console.log(heap.arr)
            heap.shift(v)
        }
    }) 
    console.log('end', heap.arr)
    return heap.getTop()
};
findKthLargest([3,2,3,1,2,4,5,5,6], 4)

